function bubbleSort1(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        console.log('do1');
        for (let j = 0; j < arr.length - i - 1; j++) {
            console.log('do1');
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

// 优化
function bubbleSort2(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        console.log('do2');
        let isSorted = true;
        for (let j = 0; j < arr.length - i - 1; j++) {
            console.log('do2');
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }
    }
    return arr;
}

function bubbleSort3(arr) {
    let lastExchangeIndex = 0;
    let sortBorder = arr.length - 1;
    for (let i = 0; i < arr.length - 1; i++) {
        console.log('do3');
        let isSorted = true;
        for (let j = 0; j < sortBorder; j++) {
            console.log('do3');
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSorted = false;
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if (isSorted) {
            break;
        }
    }
    return arr;
}

function cocktailSort(arr) {
    let sorted = true;
    for (let i = 0; i < Math.floor(arr.length / 2); i++) {
        // 奇数轮
        for (let j = i; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                sorted = false;
            }
        }
        if (sorted) {
            break;
        }
        // 偶数轮
        sorted = true;
        for (let j = arr.length - i - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                const temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                sorted = false;
            }
        }
        if (sorted) {
            break;
        }
    }
}

const arr = [5,8,6,3,9,2,1,7];
// const res1 = bubbleSort1(arr); // 一共循环35次 1+2+3+4+5+6+7+8 - 1

const arr2 = [1,2,3];
// const res21 = bubbleSort1(arr2); // 5次
// const res22 = bubbleSort2(arr2); // 3次

const arr3 = [3,2,1,4,5,6];
// const res31 = bubbleSort1(arr3); // 原始20次
// const res32 = bubbleSort2(arr3); // 优化后14次
// const res32 = bubbleSort3(arr3); // 优化后9次

// const arr3 = [3,4,2,1,5,6,7,8];
// const res3 = bubbleSort3(arr);
// console.log(res3);

const arr4 = [2,3,4,5,6,7,8,1]; // 大部分已经有序
cocktailSort(arr4);
console.log(arr4);

function quickSort(arr, startIndex, endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    const pivotIndex = partition(arr, startIndex, endIndex);
    // const pivotIndex = partitionSingle(arr, startIndex, endIndex);
    quickSort(arr, startIndex, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, endIndex);
}

// 之所以称为partition，是因为把数组分为了两个部分，左小右大，且返回pivot的index
function partition(arr, startIndex, endIndex) {
    let pivot = arr[startIndex];
    let left = startIndex;
    let right = endIndex;
    while (left != right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        while (left < right && arr[left] <= pivot) {
            left ++;
        }
        if (left < right) {
            const temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    arr[startIndex] = arr[left];
    arr[left] = pivot;
    return left;
}

function partitionSingle(arr, startIndex, endIndex) {
    let pivot = arr[startIndex];
    let mark = startIndex;
    for (let i = startIndex + 1; i <= endIndex; i++) {
        if (arr[i] < pivot) {
            mark++;
            const temp = arr[i];
            arr[i] = arr[mark];
            arr[mark] = temp;
        }
    }
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

const quickArr = [4,4,6,5,3,2,8,1];
quickSort(quickArr, 0, quickArr.length - 1);
console.log(quickArr);

// 非递归实现快速排序
// [
//     {
//         startIndex: 0,
//         endIndex: arr.length - 1
//     }
// ]

function quickSortStack(arr, startIndex, endIndex) {
    const stack = new Array();
    stack.push({
        startIndex,
        endIndex
    });
    while (stack.length > 0) {
        const { startIndex, endIndex } = stack.pop();
        const pivotIndex = partitionSingle(arr, startIndex, endIndex);
        if (startIndex < pivotIndex - 1) {
            // leftParam
            stack.push({
                startIndex,
                endIndex: pivotIndex - 1
            });
        }
        if (endIndex > pivotIndex + 1) {
            // rightParam
            stack.push({
                startIndex: pivotIndex + 1,
                endIndex
            });
        }
    }
}

// const quickStackArr = [4,4,6,5,3,2,8,1];
// quickSortStack(quickStackArr, 0, quickStackArr.length - 1);
// console.log(quickStackArr);